package edu.siu.math.egut.util;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInput;
import java.io.ObjectInputStream;
import java.io.ObjectOutput;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//import edu.siu.math.egut.main.SectionIntegral;

/**
 * 
 * A data structure which represents, for our purposes, a split, connected,
 * simply connected simple algebraic group.
 * Essentially a bundle of important structural invariants of such an object as
 * follows: 
 * (1) a list of positive roots (defining an order on this set) 
 * (2) a list of negative roots 
 * (3) a "Cayley table" for addition of roots.
 * (4) a matrix containing the structure constants N(a,b) for a,b,
 * positive roots. 
 * (5) a "Cayley table" for commutator of simple unipotents
 * (6) the lengths of the roots (normalized so that short roots are length 1) 
 * (7) the Cartan matrix
 * (8) the matrix representing the Weyl group invariant inner
 * product with respect to the basis of simple roots, normalized so that the
 * entries are integers with gcd 1.
 * 
 * 
 * @author Joe Pleso
 * @author Joseph Hundley
 * 
 */
public class Group implements Serializable{

    
/**
     * 
     */
    private static final long serialVersionUID = 1L;
/* 
 * The present implementation makes use of serialization so that important structural information
 * may be computed once and stored for later reference.  The data for each of the five simple 
 * exceptional groups is stored in a file.  Here, we declare the names of those files as constants.
 */
    private static final String E8_FILENAME = "E8.ser";
    private static final String E7_FILENAME = "E7.ser";
    private static final String E6_FILENAME = "E6.ser";
    private static final String F4_FILENAME = "F4.ser";
    private static final String G2_FILENAME = "G2.ser";
    /**
     * 
     */

/*
 * Write the group to a file.  (Serialize.)
 */
    private static void saveGroup (String filename, Group g){
        
        try{
              //use buffering
              OutputStream file = new FileOutputStream( filename);
              OutputStream buffer = new BufferedOutputStream( file );
              ObjectOutput output = new ObjectOutputStream( buffer );
              try{
                output.writeObject(g);
              }
              finally{
                output.close();
              }
            }  
            catch(IOException ex){
              System.err.println(ex);
            }
        
    }
    /* 
     * Load the group from a file.  (Deserialize.)
     */
    private static Group loadGroup (String filename){
        
            
            try{
              //use buffering
              InputStream file = new FileInputStream( filename );
              InputStream buffer = new BufferedInputStream( file );
              ObjectInput input = new ObjectInputStream ( buffer );
              try{
                //deserialize the List
                return (Group)input.readObject();
                 
              }
              finally{
                input.close();
              }
            }
            catch(ClassNotFoundException ex){
              System.err.println(ex);
            }
            catch(IOException ex){
                System.err.println(ex);
            }
        

            
            return null;
        
        
    }
/*
 * These constants are related to the algorithm by which commutators of simple 
 * unipotents are computed.  We store a Cayley table of commutators
 * (x_a(r), x_b(s)) where a and b range over roots.  Then, to compute
 * (x_a(p), x_a(q)) for arbitrary polynomials p and q, we simply substitute
 * p for r and q for s.  
 * 
 * Of course, this algorithm will produce incorrect results if the String "s"
 * appears as a variable in the Polynomial p.  Therefore, instead of "s" we
 * use Monomial.RESERVED_VARIABLE, an awkward String which the user is unlikely
 * to want to, and has been warned not to, use as a variable.
 */
    private final static String rString = "r";
    private final static String sString = Monomial.RESERVED_VARIABLE;

    /* The default method to access a group takes two arguments:  a String,
     * and an integer.  The String should be the name of a file containing
     * a serialized Group object.  If no such file is found, the integer
     * can be used to recover the information, using the fact that a
     * simple exceptional group is determined by its rank. 
     * 
     */
    private static Group getGroup(String filename, int rank) {
	
	// try to load the group from the file.
	Group g  = Group.loadGroup(filename) ;// if the group is not found.
	 if (g == null)
	{
	     // let the user know what is going on.
	    System.out.println("Generating " + filename + "...");
	    
	    // call the constructor in order to get the group.
	    g = new Group(rank);
	    // write the file.
	     Group.saveGroup(filename, g);
	}

	return g;

    }
    
    /* Key invariants for each group are computed once and stored.  Under the 
     * current implementation (April 13, 2010) all key data associated to G2 
     * will be stored in a file called "G2.ser." 
     * 
     */
    @SuppressWarnings("unused")
    private static String getFileName( final int rank){
	switch( rank ){
	case 2:
	    return G2_FILENAME;
	case 4: 
	    return F4_FILENAME;
	case 6:
	    return E6_FILENAME;
	case 7:
	    return E7_FILENAME;
	case 8:
	    return E8_FILENAME;
	}
	throw new RuntimeException();
	// (For our purposes, any attempt to work with "the exceptional 
	//group of rank 5" is an unrecoverable error.)
    }

    /**
     * Returns the object in our Group class which models the unique simple exceptional group 
     * of the specified rank.
     * @param rank must equal 2,4,6,7, or 8.
     * @return the unique simple exceptional group of the specified rank.
     */
    public static final Group getGroup( int rank){
	switch( rank ){
	case 2:
	    return G2;
	case 4: 
	    return F4;
	case 6:
	    return E6;
	case 7:
	    return E7;
	case 8:
	    return E8; 
	}
	throw new RuntimeException();
	// (For our purposes, any attempt to work with "the exceptional 
	//group of rank 5" is an unrecoverable error.)

    
    }
    
    /*  Next, we declare the five static objects of this class,
     * representing the five simple exceptional groups.
     */
     
    /**
     * The static group E8.
     */
    public static final Group E8 = getGroup(Group.E8_FILENAME, 8); 

    /**
     * The static group E7.
     */
    public static final Group E7 = getGroup(Group.E7_FILENAME, 7);

    /**
     * The static group E6.
     */
    public static final Group E6 = getGroup(Group.E6_FILENAME, 6);

    
    /**
     * The static group G2.
     */
    public static final Group G2 = getGroup(Group.G2_FILENAME, 2);
    /**
     * The static group F4.
     */
    public static final Group F4 = getGroup(Group.F4_FILENAME, 4);

    
    /**
     * Returns (a,a), where ( , ) is the Weyl-invariant inner product and a is the root which appears at
     * position i in the root list.
     * 
     * @param i an integer, should be between 0 and the number of positive roots of the group minus 1.
     * @return (positiveRoots[i], positiveRoots[i])
     */
    public int getNormSquare(int i) {
	
	/* Let N denote the number of positive roots of our group.  Then "root i" 
	 * is a positive root if i is between 0 and N-1 inclusive, and a 
	 * negative root if i is between N and 2N - 1 inclusive.  
	 * 
	 *  We have stored the norm squares of the positive root.  If this 
	 *  method is passed an integer which points to a negative root,
	 *  we pass back the norm square of the corresponding positive 
	 *  root-- which is the correct answer.
	 * 
	 */
	
	if( positiveRoots.length <= i&& i  < 2* positiveRoots.length)
	    return normSquares[i-positiveRoots.length];
	return normSquares[i];
	/* Remark:  Passing this method and argument which is not 
	 * between 0 and 2N-1 inclusive results in an Array index out
	 * of bounds, which seems sound.
	 */
    }

    
    /**
     *  Returns the commutator [s1,s2]=s1 s2 s1^{-1} s2^{-1} of two Sunipotents, 
     *  as a list of sunipotents.
     *  (In practice this is more useful than returning a Unipotent.) 
     *  
     *  (A simple unipotent, or sunipotent, element of an exceptional group is
     *  an element which is of the form x_\alpha(r), where \alpha is a root 
     *  and r is an element of the additive group-scheme \G_a.  In order to 
     *  work with these symbolically, we represent r by an element of the class
     *  Polynomial.)
     * 
     * @param s1 the first sunipotent
     * @param s2 the second sunipotent
     * 
     * @return the commutator [a,b]
     * 
     * 
     */

    /* 
     * This implementation uses a Cayley table of pre-computed 
     * commutators [x_a(r), x_b(s)].  The steps are as follows:
     * (1) locate the correct pre-computed commutator, 
     * corresponding to a= s1.getRoot(), b = s2.getRoot()
     * (2) substitute the argument of s1 for r and the argument
     * of s2 for s.
     * 
     * The Cayley table itself is, conceptually, a two dimensional 
     * array of lists of sunipotent elements indexed by pairs 
     * of positive roots.   The (a,b) entry in this table is 
     * [x_a(r), x_b(s)] (or rather, a list of Sunipotents representing
     * the underlying data of this Unipotent object).
     * 
     * However, the Cayley table is not stored in this format.
     * 
     * Rather, it is stored as a (one-dimensional) List of 
     * lists of Sunipotents.  Thus the substeps of step (1) are
     * (1a) convert (a,b) to an integer,
     * (1b) obtain the pre-computed commutator corresponding to this 
     * integer.
     * 
     * 
     * 
     */
    
    public List<Sunipotent> commutator(Sunipotent s1, Sunipotent s2) {
	int signOffset = 0;
	int aPos;
	int bPos;
	if (!isPositive(s1.getRoot())) {
	    signOffset += 1;
	    try {
		aPos = findIndex(negative(s1.getRoot()));
	    } catch (NotARootException e) {
		throw new RuntimeException();
	    }
	} else {
	    aPos = findIndex(s1.getRoot());
	}
	if (!isPositive(s2.getRoot())) {
	    signOffset += 2;
	    try {
		bPos = findIndex(negative(s2.getRoot()));
	    } catch (NotARootException e) {
		throw new RuntimeException();
	    }
	} else {
	    bPos = findIndex(s2.getRoot());
	}

	/*
	 * m(a,b) = n^2 * signOffset + n*i + j
	 */
	List<Sunipotent> replacement = replacements.get(positiveRoots.length
		* positiveRoots.length * signOffset + positiveRoots.length * aPos + bPos);

	/* keep in mind that replacement will "usually" be the Empty List,
	 * because most pairs of Sunipotents commute.
	 */
	
	List<Sunipotent> result = new ArrayList<Sunipotent>();
	if( replacement != null){
		
	    
	for (Sunipotent s : replacement) {
	    Polynomial p = s.getArgument();
	    try {
		p = p.replace(rString, s1.getArgument());
		p = p.replace(sString, s2.getArgument()); // (observe that an incorrect result will be 
		    //  obtained if sString was used in a.getPolynomial)

	    } catch (BadSubstitutionException e) {
		// Bad substitution will not occur.
		e.printStackTrace();
	    }

	    result.add(Sunipotent.create(s.getRoot(), p));
	}
	}
	return result;
    }// end of commutator method.

    
    /* 
     * This method computes the commutator of two simple unipotent elements of 
     * an exceptional group from the definitions.  It is run once for each 
     * pair of roots for each group as part of the initialization process for
     * the corresponding Group object, and the data is stored.  Thenceforth,
     * the commutator will be computed by substitution using the stored data.
     */
    private List<Sunipotent> internalCommutator(Sunipotent s1, Sunipotent s2) {

	/*
	 * Instantiate a list of Sunipotents 
	 */
	List<Sunipotent> result = new ArrayList<Sunipotent>();

	// extract the underlying data of the two Sunipotents
	Polynomial p1 = s1.getArgument();
	Polynomial p2 = s2.getArgument();
	int[] a =s1.getRoot();
	int[] b = s2.getRoot();


	/* (x_a(p1), x_b(p2) ) is contained in the product of the one-dimensional 
	 * unipotent groups U_c corresponding to roots of the form c = m*a + n*b, 
	 * where m and n are both positive.
	 * 
	 * of course, the possibilities for m and n are limited.  
	 * 
	 * indeed, consider the subgroup of G generated by U_a, U_b, U_{-a} and U_{-b}.
	 * it is simply connected, semisimple, and of rank 2, hence it is isomorphic 
	 * to one of the groups G2, Sp(4), SL(3) or SL(2) x SL(2).
	 * 
	 * suppose that it is SL(3) and that a+b is a root.
	 * then U_a and U_b generate a group U isomorphic
	 * to the maximal unipotent subgroup U' of SL(3), and there is an isomomorphism 
	 * U -> U' such that 
	 * 
	 * x_a(r) ->	1 r 0	x_b(s) -> 	1 0 0	
	 *		0 1 0 			0 1 s	
	 *		0 0 1 			0 0 1.
	 *
	 *Let X_a and X_b denote the elements of the Chevalley basis for the LiE 
	 *algebra of G corresponding to a and b.  Thus x_a( r) = exp( r X_a ),
	 * x_b( r ) = exp( r X_b ).
	 * 
	 * Now, the definition of the structure constants is that 
	 * [X_a, X_b] = N(a,b) X_{a+b}.  The isomorphism U -> U' fixed above induces
	 * an isomorphism on the corresponding Lie algebras such that

	 *  X_a	 ->	0 1 0	X_b	 -> 	0 0 0	
	 *		0 0 0 			0 0 1	
	 *		0 0 0 			0 0 0,
	 * and so
	 * 
	 * N(a,b) X_{a+b} -> 	0 0 1
	 * 			0 0 0
	 * 			0 0 0.
	 * 
	 * This proves that ( x_a(r) , x_b(s) ) = x_{a+b}( N(a,b) r s).
	 * 
	 * In general, the formulae which we use can be expressed as 
	 * follows:
	 * 
	 * (x_a(r),x_b(s)) 
	 * 	=  	x_{a+b}( N(a,b) r s ) 
	 * 		x_{2a+b}( N(a,b) N(a, a+b)/2 r^2 s ) 
	 * 		x_{3a+b}(N(a,b) N(a, a+b) N(a, 2a+b)/6  r^3 s)
	 * 		x_{3a+2b}( N(a,b) N(a, a+b) N(a, 2a+b) N(b, 3a+b)/3 r^3 s^2) 
	 * 		x_{a+2b}( N(a,b) N(b, a+b)/2 r s^2 )
	 * 		x_{a+3b}(N(a,b) N(b, a+b) N(b, a+2b)/6  r s^3 )
	 * 		x_{2a+3b}( -N(a,b) N(b, a+b) N(b, a+2b)N(a, a+3b)/6 r^2 s^3),
	 * 
	 * keeping in mind that for any particular choice of a and b, at least 3 
	 * of these terms will be trivial.
	 * 
	 * We sketch a proof. Let G(a,b) be the group generated by U_a, U_b, U_{-a}, and U_{-b}.
	 * Then G(a,b) is isomorphic to SL(2) x SL(2), SL(3), Sp(4) or G2, and there
	 * is an isomorphism which maps U_a and U_b into the standard maximal unipotent 
	 * subgroup, such that a becomes a simple root.  This leaves only finitely many 
	 * possibilities to check, most of which are trivial.
	 *  
	 */

	// compute a+b
	int[] ab;
	ab = sums.add(a,b);

	// see if it's a root.  note that if a+b is not a root we are DONE:  the two Sunipotents commute.
	// (unless a = -b.  in this case, we have an error:  out "Unipotent" is not actually unipotent!)
	if( isRoot(ab)){
	    Polynomial pab =p1.times(p2);
	    int cab =getStructureConstant(a,b);


	    result.add(Sunipotent.create(ab, pab.times( cab )));// add the Suni for a+b

	    // check if 2a+b is a root

	    int[] aab;
	    aab = sums.add(a, ab);
	    if( isRoot( aab) ){
		Polynomial paab = pab.times(p1); // = p1^2 p2 
		int caab = cab*getStructureConstant(a, ab) /2; // = N(a,b) N(a, a+b)/2
		result.add(Sunipotent.create(aab, paab.times(caab)));// = x_{2a+b}( N(a,b) N(a, a+b)/2 p1^2 p2  )

		// find out if 3a+b is a root

		int[] aaab = sums.add(a, aab);
		if(isRoot(aaab)){
		    // add the Suni for 3a+b
		    Polynomial paaab = paab.times(p1); // = p1^3 p2
		    int caaab =caab*getStructureConstant(a,aab)/3; // = N(a,b) N(a, a+b) N(a, 2a+b)/6

		    result.add(Sunipotent.create(aaab, paaab.times(caaab)));
		  //= x_{3a+b}(N(a,b) N(a, a+b) N(a, 2a+b)/6  p1^3 p2)

		    // find out if 3a+2b is a root

		    int[] aaabb = sums.add(b, aaab);
		    if( isRoot(aaabb))
		    {

			// add the Suni for 3a+2b
			Polynomial paaabb = paaab.times(p2);// = p1^3 p2^2
			int caaabb = 2*caaab*getStructureConstant(b, aaab);// = N(a,b) N(a, a+b) N(a, 2a+b) N(b, aaab)/3

			result.add(Sunipotent.create( aaabb, paaabb.times(caaabb)));
			// = x_{3a+2b}( N(a,b) N(a, a+b) N(a, 2a+b) N(b, aaab)/3 p1^3 p2^2)
			
		    }// end if isRoot 3a+2b
		}// end if isRoot aaab
	    }// end if isRoot aab

	    int[] abb;
	    abb = sums.add(ab, b); // = a+2b
	    if( isRoot(abb))
	    {
		Polynomial pabb = pab.times(p2);// = p1 p2^2 
		int cabb = cab*getStructureConstant(b, ab) /2; //= N(a,b) N(b, a+b)/2
		result.add(Sunipotent.create(abb, pabb.times(cabb)));// =x_{a+2b}( N(a,b) N(b, a+b)/2 p1 p2^2 ).

		// find out if 3a+b is a root

		int[] abbb = sums.add(b, abb);// = a+3b 
		if(isRoot(abbb)){
		    // add the Suni for 3a+b
		    Polynomial pabbb = pabb.times(p2);// = p1 p2^3 
		    int cabbb =cabb*getStructureConstant(b,abb)/3;// = N(a,b) N(b, a+b) N(b, a+2b)/6

		    result.add(Sunipotent.create(abbb, pabbb.times(cabbb)));
		    // = x_{ a+ 3b}(N(a,b) N(b, a+b) N(b, a+2b)/6  p1 p2^3 ) 

		    // find out if 3a+2b is a root

		    int[] aabbb = sums.add(a, abbb);// = 2a + 3b
		    if( isRoot(aabbb))
		    {

			// add the Suni for 3a+2b
			Polynomial paabbb = pabbb.times(p1); // = p1^2 p2^3 
			int caabbb = -1*cabbb*getStructureConstant(a, abbb); //= -N(a,b) N(b, a+b) N(b, a+2b)N(a, a+3b)/6

			result.add(Sunipotent.create( aabbb, paabbb.times(caabbb)));
			// = x_{2a+3b}( -N(a,b) N(b, a+b) N(b, a+2b)N(a, a+3b)/6 p1^2 p2^3)
			
			
		    }// end if isRoot 3a+2b
		}// end if isRoot aaab
	    }// end if isRoot aab
	}// end if isRoot ab
	return result;
    }

    /**
     * Finds the index of an int[] in an int[][].  Our application is to looking for a specific 
     * root in a list of roots (e.g., the roots which determine a unipotent subgroup), and this 
     * motivates the names of the variables.
     * 
     * @param roots an int[][] to search in
     * @param root an int[] to find in roots
     * @return the index such that roots[index]==root is true, or -1 if a match
     *         was not found
     */
    private int findIndex(int[][] roots, int[] root) {
	for (int i = 0; i < roots.length; i++)
	    if (Arrays.equals(root, roots[i]))
		return i;
	return -1;
    }
/**
 * Finds the index of an int[] in the specific int[][] "roots" given by this group.
 */
    private int findIndex(int[] root) {
	return findIndex(roots, root);
    }

    /**
     * Adds two roots from the same group.
     * 
     * @param a  the first root
     * @param b the second root
     * 
     * @return the sum of the roots (only if it is a root)
     * @throws NotARootException
     *             thrown if the sum is not a root
     */
  
    /*
    public int[] add(int[] a, int[] b) throws NotARootException {
	boolean aPos = isPositive(a);
	boolean bPos = isPositive(b);
	int[] c;
	if (!(aPos ^ bPos)) {
	    if (aPos) {
		c = sums.add(a, b);
	    } else {
		c = negative(sums.add(negative(a), negative(b)));
	    }

	} else {
	    if (aPos) {
		int sign = Algorithms.getWeight(a) + Algorithms.getWeight(b);
		c = sums.subtract(a, negative(b));
		if (sign < 0)
		    c = negative(c);
	    } else {
		int sign = Algorithms.getWeight(a) + Algorithms.getWeight(b);
		c = sums.subtract(negative(a), (b));
		if (sign < 0)
		    c = negative(c);
	    }
	}
	if (isRoot(c))

	    return c;
	throw new NotARootException();
    }
*/
    
    
    /**
     * Returns the coefficient from the structure constants matrix for given
     * roots a and b.
     * 
     * 
     * @param a the first root
     * @param b the second root
     * 
     * @return the coefficient from the structure constants matrix
     */
    public int getStructureConstant(int[] a, int[] b) {
	int[] c;
	    c = sums.add(a, b);
	if (isRoot(c)) {
	    if (isPositive(a))
		if (isPositive(b))// then the structure constant is stored.  read it.
		    return structureConstantsMatrix.get(a, b);
		else {
		    if (isPositive(c)) {			// a >0, b <0, a+b >0
			try {					// formula is 
			    b = negative(b);			// N(a,b) = - (a+b,a+b) N( -b, a+b) /(a,a)
			} catch (NotARootException e) {		// (which is an integer:  (a+b,a+b)N( -b, a+b)
			    throw new RuntimeException();	// is divisible by (a,a).
			}
			if ((getNormSquare((c))) * structureConstantsMatrix.get(b, c) % getNormSquare(a) != 0) {
			    throw new RuntimeException(			// verify that (a+b,a+b)N( -b, a+b)
				    "sign algorithm is no good.  ");	// is divisible by (a,a).
			}
			return -1 * (getNormSquare((c))) * structureConstantsMatrix.get(b, c) // apply formula.
				/ getNormSquare(a);
		    } else// that is, if c is negative.				// case a>0, b<0, a+b <0							
			try {							// formula is
			    return this.getStructureConstant(negative(b),	// N(a,b) = N(-b,-a).
				    negative(a));
			} catch (NotARootException e) {
			    throw new RuntimeException();
			}
		}// end case b < 0, 
	    // end case a >0.
	    else // i.e. if a < 0
	    {
		if (isPositive(b)) 						// case a<0, b>0
		    return -1 * this.getStructureConstant(b, a);		// N(a,b) = -N(b,a)
		else								
		    try {							// case a<0, b<0
			return this.getStructureConstant(negative(b),		// N(a,b) = N(-b, -a).
				negative(a));
		    } catch (NotARootException e) {
			throw new RuntimeException();
		    }
	    }
	} else
	    return 0;
    }

    /** 
     * Checks whether a given int[] is a positive root
     * @param root  an int[] (putatively, a root)
     * @return true if root corresponds to a positive root 
     */ 
      boolean isPositive(int[] root) {
     
	return findIndex(positiveRoots, (root)) >= 0;
    }

    /**
     * Checks to see if the argument that is passed to this method is, in fact,
     * a root in the root system of this group.
     * 
     * @param root check to see if this vector is a root in the root system
     * @return true if the vector was a root
     * 
     * 
     */

    public boolean isRoot(int[] root) {

	return findIndex(roots, root)>-1;
   }

 
    /**
     * Multiplies every vector in a list by -1.
     * 
     * @param v   list of vectors
     * @return a new list with each element multiplied by -1.
     */
    private static int[][] negative(int[][] v) {
	int[][] result = new int[v.length][];
	for (int i = 0; i < result.length; i++) {
	    result[i] = new int[v[i].length];
	    for (int j = 0; j < v[i].length; j++) {
		result[i][j] = (-1 * v[i][j]);
	    }
	}
	return result;
    }

    /**
     * Negates a root.
     * 
     * @param root a root in the group
     * @return the negative of the specified root
     * @throws NotARootException thrown if the root is not a root
     */
    public int[] negative(int[] root) throws NotARootException {
	if (!isRoot(root)){
	    System.out.print(edu.siu.math.egut.io.Algorithms.tupleToString(root)+" is not a root.");
	    throw new NotARootException();
	}
	int i = findIndex(root);
	return this.roots[((i+positiveRoots.length)%(roots.length))];  
	/* the list roots contains all the positive roots and then all of their negatives in the same order.
	 * so we just add the number of positive roots and take the result modulo the total number of roots.
	 */
    }

    /**
     * Returns a very short string representing a root, which may be positive or
     * negative.
     * 
     * 
     * 
     * @param root the root to convert to a string
     * @return a short string representation of the root
     */
    public String toString(int[] root) {

	StringBuffer sb = new StringBuffer();
	int sgn = 1;
	if (!isPositive(root))
	{
	    sb.append("-");
	    sgn = -1;
	}
	for (int i = 0; i < root.length; i++)
	    sb.append(sgn*root[i]);
	return sb.toString();

    }

    /**
     * Returns a string representation for the specified sunipotent in the
     * specified group.
     * 
     * @param s the sunipotent to convert to a string
     * @return the string representation of s
     */
    public String toString(Sunipotent s) {
	Group g = this;
	return "x_" + g.toString(s.getRoot()) + "(" + s.getArgument() + ")";
    }

    private final int[][] positiveRoots;

    private final int[][] negativeRoots; // = Algorithms.negative(roots);
    
    private final int[][] roots;

    private final VectorCayleyTable sums;// =

    // new VectorCayleyTable (roots);
    private final StructureConstantsMatrix structureConstantsMatrix;// =

    private final List<List<Sunipotent>> replacements;
 
    private final int[] normSquares;

    private final int[][] cartan;

    private final int[][] weylInvtInnProdMatrix;
     /**
     * Returns the matrix of the Weyl invariant inner product normalized so that 
     * short roots have length 2.
     * 
     * @return Weyl Invariant Inner Product Matrix, as int[][]
     */
    public int[][] getWeylInvtInnProdMatrix() {
	return weylInvtInnProdMatrix;
    }
    
    /**
     * Computes the normalized Weyl invariant inner product of two roots.  The inner product (, ) is normalized so 
     * that (a,a) =1 for short roots.
     * @param a an int[], which should be a root of the relevant group (in terms of the basis of simple roots).
     * @param b an int[], which should be a root of the relevant group (in terms of the basis of simple roots).
     * @return  (a,b), where (,) is the normalized Weyl-invariant inner product.
     */
    public int weylInvtInnProd(int[] a, int[] b){
	if(a.length != roots[0].length || b.length != roots[0].length)
	    throw new RuntimeException(" Weyl Invariant inner product called with vectors of wrong length.");
	int sum = 0;
	for( int i = 0 ; i < roots[0].length; i++)
	    for( int j = 0; j < roots[0].length; j++)
		sum += a[i]*b[j]*weylInvtInnProdMatrix[i][j];
	return sum;
    }
/**
 * Constructor for exceptional groups, which are, for our purposes, completely determined by their ranks.
 * For the most part, the relevant data is simply read in from the file EGData.java.
 * 
 * @param rank  The semisimple rank of the desired exceptional group. Must equal 2,4,6,7, or 8.  For 
 * any other value a runtime error will be thrown.
 */
    private Group(int rank) {
	
	/* First part is pretty straightforward.
	 */

	this.positiveRoots = EGData.positiveRoots(rank);// initialize positiveRoots from list hard-coded in EGData.
	this.negativeRoots = negative(positiveRoots); // negative roots are the negatives of the positive ones (in order).
	roots = new int[2*positiveRoots.length][rank];  // now simply concatenate the two into one big list of roots.
	for( int i = 0 ; i < positiveRoots.length; i++)
	    for( int j = 0 ; j < rank ; j++)
		roots[i][j] = positiveRoots[i][j];
	for( int i = positiveRoots.length; i < roots.length; i++)
	    for( int j = 0 ; j < rank ; j++)
		roots[i][j] = negativeRoots[i-positiveRoots.length][j];
	
	this.sums = new VectorCayleyTable(roots); // form a Cayley table for addition of roots.  

	this.cartan = EGData.cartan( rank); // read the Cartan matrix from EGData.
	this.weylInvtInnProdMatrix = EGData.weylInvtInnProd( rank ); // read the matrix of the normalized Weyl-invariant
									// from EGData
	this.structureConstantsMatrix = EGData.structureConstantsMatrix( rank); // get the matrix of structure constants
	this.normSquares = EGData.normSquares(rank); // read the norm squares.
	
	/*
	 * The rest of this Constructor is spent on initializing a
	 * "Cayley table" for symbolically computing the commutator of two simple unipotent
	 * elements the given group.
	 * 
	 * Conceptually, this should be thought of as a two dimensional array, indexed on 
	 * each side by the set of positive roots.  The entry in this array corresponding 
	 * to the pair of roots (a,b) is a list of Sunipotents corresponding to the commutator 
	 * 
	 * ( x_a( rString ), x_b( sString ) ) = x_a(rString) x_b( sString) x_a( -rString ) x_b( -sString ).
	 * 
	 * step 1:  build two polynomials, rPoly and sPoly, each of which consists of the correspoding variable
	 * to the first power.
	 */
	Polynomial rPoly;
	Polynomial sPoly;
	    rPoly = Polynomial.create(rString);
	
	 sPoly = Polynomial.create(sString);
	 
	 // initialize an ArrayList of  Lists of Sunipotents.  This is our table.
	replacements = new ArrayList<List<Sunipotent>>();
	// although the table is conceptually a two dimensional object.  We store it
	// in a simple list.
	
	
	// now we fill in the "entries."  Note that since we are converting a two dimensional 
	// array into a one-dimensional list, order matters.
	
	// first we proceed through pairs (a,b) both positive.

	for (int i = 0; i < positiveRoots.length; i++) {

	    for (int j = 0; j < positiveRoots.length; j++) {
		// the commutator is computed using the private method "internalCommutator"
		// however, internalCommutator is coded using a formula which is only valid
		// if b is neither a nor -a.  
		if (i != j){
		    replacements.add(this.internalCommutator(Sunipotent.create(
			    positiveRoots[i], rPoly), Sunipotent
			    .create(positiveRoots[j], sPoly)));
		} else
		    replacements.add(null); // if i=-j, we just put null in the table.  
		// this correctly reflects the fact that the image of x_a is a commutative group.
	    }
	}
	
	// next the pairs where a< 0, b >0
	for (int i = 0; i < positiveRoots.length; i++) {

	    for (int j = 0; j < positiveRoots.length; j++) {
		if (i != j) {
		    replacements.add(this.internalCommutator(Sunipotent.create(
			    negativeRoots[i], rPoly), Sunipotent.create(
			    positiveRoots[j], sPoly)));
		} else
		    replacements.add(null); // it is certainly not the case that the commutator of 
		/* x_a(r) and x_{-a}(s) is trivial.  What is true is that no maximal unipotent
		 * subgroup will contain both.  An attempt to take such a commutator is a logic
		 * error.
		 */
	    }
	}
	
	// next the pairs where  a >0, b <0
	for (int i = 0; i < positiveRoots.length; i++) {

	    for (int j = 0; j < positiveRoots.length; j++) {
		if (i != j) {
		    replacements.add(this.internalCommutator(Sunipotent.create(
			    positiveRoots[i], rPoly), Sunipotent.create(
			    negativeRoots[j], sPoly)));
		} else
		    replacements.add(null); 
	    }
	}
	
	// finally the pairs where a<0,b<0.
	for (int i = 0; i < positiveRoots.length; i++) {

	    for (int j = 0; j < positiveRoots.length; j++) {
		if (i != j) {
		    replacements.add(this.internalCommutator(Sunipotent.create(
			    negativeRoots[i], rPoly), Sunipotent.create(
			    negativeRoots[j], sPoly)));
		} else
		    replacements.add(null);
	    }
	}

    }

    /**
     * Returns the list of negative roots.
     * 
     * @return the list of negative roots
     */
    public int[][] getNegativeRoots() {

	return (negativeRoots);
    }

    /**
     * Returns the list of positive roots.
     * 
     * @return the list of positive roots.
     */
    public int[][] getPositiveRoots() {

	return (positiveRoots);
    }

    /**
     * Returns the list of all roots.  (It will be the positive roots in the order they appear in EGData, 
     * followed by their negatives in the same order.)
     * 
     * @return the list of all roots.
    */
    public int[][] getRoots(){
	return roots;
	
    }
    /**
     * Gets the semisimple rank of this group.
     * 
     * @return the rank of the group
     * 
     * 
     */

    public int getRank() {

	return roots[0].length;
    }

    /**
     * Determines whether a collection u = { a1, a2, ... an} 
     * of roots of G defines a unipotent 
     * subgroup of the G, i.e., if the set of all elements of 
     * G of the form 
     * x_{a1}(r1) ... x_{an} (rn) 
     * is closed under multiplication.
     * 
     * An equivalent condition is that for a, b in u, either a+b is 
     * in u, or a+b is not a root.
     * 
     * @param u a set of roots of G. 
     * @return true iff a+b is either in u or not a root for all a b in u.
     */
   public boolean definesGroup(int[][] u){
   for( int i = 1; i < u.length; i++)
       for( int j = 0 ; j< i; j++)
       {
	   int[] c = sums.add(u[i],u[j]);
       
	   if(c != null && findIndex(u,c) == -1 )// c!=null means the sum of the two ints in question is a root.
	       return false;			// findIndex(u, c)== -1 means that it is not in u. 
       }
   return true;
       
   }

    /**
     * The Cartan matrix (an int[][]).  For example, G2.getCartan() returns  {{ 2, -1 },{ -3, 2 }}.
     * @return  The cartan matrix.
     */
    public int[][] getCartan() {
        return cartan;
    }

 
    /**
     * Gets the norm square of a given root a, i.e., (a,a) where (,) is the normalized
     * Weyl invariant inner product.  
     * @param a should represent a root of the desired group in terms of the basis of simple roots
     * @return |a|^2 (norm defined in terms of Weyl invariant inner product)
     */
    public int getNormSquare(final int[] a) {
	
	return normSquares[findIndex(a)%positiveRoots.length];
    }

    
    /**
     * Image of an element of the root lattice under one of the 
     * simple reflections in the Weyl group.
     * @param i index of a simple root
     * @param r element of the root lattice.
     * @return s_{alpha_i} (r)  (as a vector expressed in terms of the 
     * basis of simple roots.)
     */
    public int[] simpleReflection( int i, int[] r){
	if( r.length != this.getRank())// then something is fishy..
	    throw new RuntimeException("Attempt to reflect a vector of dimension unequal to the rank of the ambient group.");
	
	/*The formula is s_a(b) = b - 2(b,a)/(a,a) a
	 * In our case, since a is a basis vector, we are assured 
	 * that the only possible change is at the i-th place.
	 * 
	 */
	int [] ans = r.clone();
	ans[i-1] = r[i-1] - 2*this.weylInvtInnProd(r, roots[i-1])/weylInvtInnProd(roots[i-1],roots[i-1]);
	return ans;
	
    }
    
    /**
     * Computes the sign which appears when a simple unipotent is acted on by the standard representative for 
     * a simple reflection in the Weyl group.  In more detail, let a_i be a simple root and b another root.
     * Let s_i be the simple reflection in the weyl group corresponding to a_i and let S_i denote its standard
     * representative, defined as x_{a_i}(1) x_{-a_i}(-1) x_{a_i}(1).  Then 
     * 
     * S_i x_b(r) S_i^{-1} = x_{s_i(b)} (+/- r), 
     * 
     *  and this function computes that sign, returning +1 or -1.
     * 
     * @param i index of a simple reflection
     * @param b root
     * @return +1 or -1.
     * @throws NotARootException if second argument is not a root.
     */
    public int reflectionSign(int i, int[] b) throws NotARootException{
	if( i > getRank() )
	    throw new RuntimeException("Attempt to reflect on non-simple root.");
	if( !isRoot(b)){
	    System.out.println(Sunipotent.rootAsShortString(b));
	    System.exit(1);
	    throw new NotARootException();
	    
	    
	    
	    
	}
	
	if( this.getRank() < 4 )
	    return EGData.G2ReflectionSigns[i-1][findIndex(b)];
	
	/* FIXME 
	 * This needs to be checked.  How does one check it?
	 */
	if( this.getRank() == 4){
	    
	 // If a = b, then the answer is -1.
	    if( (findIndex(b)== i-1)||(findIndex(negative(b))==i-1))
		return -1;
	    
		int [] a= this.positiveRoots[ i-1 ]; // set a equal to the relevant simple root.
		
		
		
		
		if( sums.add(a,b)!=null )// check if a+b is a root
			if(  sums.add(a, sums.add(a,b))!=null)  /* if 2a+b is a root then 
			(1) a is short, while b is long, 
			(2) U_{+/-a} and U_{+/-b} generate a subgroup of F4 isomorphic Sp(4), 
			(3) we can identify a with the short simple root of Sp(4) and r with the long one, and 
			use the realization to pin down a particular isomorphism with Sp(4).  Then we can work in Sp(4).  
			
			 Working in Sp(4), we find that Ad(s_a).X_b = 1/2[X_a,[X_a,X_b]].
		
								*/
			
				return ((getStructureConstant(a,b )*getStructureConstant( a, sums.add(a,b) ))/2);
			else if( sums.subtract(b,a)!=null )
			    /*Now suppose a+b and b-a are roots, while 2a+b is not.  Then it is again the 
			     * case that U_{+/- a}, U_{+/- b} generate a group isomorphic 
			     * to Sp(4).  But now a and b are both short roots.  We identify 
			     * x_a(r) with I+r(E12-E34) and x_b(s) with I+s(E13-E24).  
			     * 
			     * Working once again in Sp(4), we find that 
			     * the action of Ad(s_a) fixes the one dimensional subspace of \frak{g} 
			     * spanned by X_b, acting on it by -1.  
			     * 
			     */
			
				return -1;
			else
			    /*
			     * If a+b is a root and neither 2a+b nor b-a is, then the same computation which 
			     * is used in the simply laced case shows that Ad(s_a).X_b = N(a,b) X_{a+b}.
			     */
				return getStructureConstant( a,b );
		else
		    // Now assume a+b is not a root.
		    
			if(sums.subtract(b,a)!=null ) // If b-a is a root, 
				if(  sums.subtract(sums.subtract(b, a), a) !=null)
				    /*If b-2a is a root as well, then we can work in Sp(4) identifying 
				     * X_b with E14 and X_a with E12-E34.
				     * One finds that Ad(n_a).X_b = E23.  
				     * It follows that 
				     * 1/2 [X_a,[X_a, Ad(n_a)X_b]] = X_b, whence
				     * N(a,b-2a)N(a,b-a)/2 *(the sign we are trying to compute ) = 1.
				     * so the sign we are trying to compute is  N(a,b-2a)N(a,b-a)/2.
				     * 
				     */
					return (getStructureConstant(a, sums.subtract(sums.subtract(b,a),a))
						*getStructureConstant(a, sums.subtract(b,a) ))/2;
				else
				    /* Now suppose b-a is a root, but a+b and b-2a are not.  
				     * Then the same proof as in the simply laced case shows
				     * Ad(s_a).X_b = -N(-a, b) X_{b-a}
				     * 
				     */
					return -1*getStructureConstant( negative(a),b);
			else
			    /*Finally, if a+b and a-b are both not roots, then one of three things holds:
			     * either a=b, a=-b, or the copy of SL(2) generated by U_{\+/- a} commutes with U_b.
			     * 
			     * In the first case the answer is -1.  This was taken care of at the beginning of 
			     * this method.  So, we are in the second case, where the answer is always 1.
			     */
				return 1;

	    
	}
	    
	
	if(Arrays.equals(b, roots[i-1])||Arrays.equals(b,getNegativeRoots()[i-1]))
	    return -1;
	if( isRoot(sums.add(b, roots[i-1])))
	    return getStructureConstant(roots[i-1], b);
	if( isRoot(sums.subtract(b, roots[i-1])))
	    return -1*getStructureConstant(negativeRoots[i-1], b);
	return 1;
	
	
    }

    /**
     * Computes the action of a Weyl group element on a collection of root vectors.  Roughly equivalent
     * to the EGUT LiE initfile command "image( vec w, mat m)."
     * @param weylAsInt integer, specifying (by interpreting its individual digits as simple reflections) an elementment
     * of the Weyl group 
     * @param m an int[][], interpreted as a list of elements of the root lattice expressed in terms of the basis
     * of simple roots.
     * @return image of m under the action of the Weyl group element specified.
     */
    public int[][] weylAction(int weylAsInt, int[][] m) {
	int[][] answer = m;
	for( int i = 0; i < m.length; i++){
	    int [] newRoot  = weylAction( weylAsInt, m[i]);
	    for( int j = 0 ; j < newRoot.length; j++)
		answer[i][j]= newRoot[j];
	    
	}
	return answer;
	
	
    }

    /**
     * Computes the action of a Weyl group element on a collection of root vectors.  Roughly equivalent
     * to the EGUT LiE initfile command "image( vec w, vec r)."
     * @param weylAsInt integer, specifying (by interpreting its individual digits as simple reflections) an elementment
     * of the Weyl group 
     * @param is int[], interpreted as element of the root lattice expressed in terms of the basis
     * of simple roots.
     * @return image of is under the action of the Weyl group element specified.
     */
    public int[] weylAction(int weylAsInt, int[] is) {
	int[] answer = is;
	while( weylAsInt > 0){
	    int i = weylAsInt%10;
	    weylAsInt = weylAsInt/10;
	    answer = simpleReflection(i,answer);
	}
	return answer;
    }
    /**
     * Returns the Group object modelling the exceptional group of the specified type.  
     * @param name should be one of 'G2', 'F4', 'E6', 'E7', E8' 
     * @return the Group object named, or null
     */
    public static Group getGroup(String name) {
	if( name.matches("G2"))
	    return G2;
	if( name.matches("F4"))
	    return F4;
	if( name.matches("E6"))
	    return E6;
	if( name.matches("E7"))
	    return E7;
	if( name.matches("E8"))
	    return E8;
	
		
	    
	return null;
    }
  
    /**
     * Returns the name of this group.  
     * @param name should be one of 'G2', 'F4', 'E6', 'E7', E8' 
     * @return the Group object named, or null
     */
    public String toString(){
	return this.getFileName(this.getRank()).substring(0,2); 
		
    }
    /**
     * @return the VectorCayleyTable for addition of roots in this group
     */
    public VectorCayleyTable getVectorCayleyTable() {
	return sums;
    }
    public Parabolic getParabolic(int i) {
	return Parabolic.create(this,i);
    }

    public int[] weylAction(int[] word, int[] root) {

	int[] answer = root;
	for (int i = word.length - 1; i > -1; i--) {
	    answer = simpleReflection(word[i], answer);
	}
	return answer;
    }
    public int weylSign(int[] word, int[] root) throws NotARootException {
	int ans = 1;
	int[] r = root;
	for( int i = word.length-1; i>-1 ; i--){
	    ans = ans * reflectionSign(word[i], r);
	    r=this.simpleReflection(word[i], r);
	}
	return ans;
    }
    
    /**
     * Returns the matrix of structure constants for the given group.
     * 
     * 
     * @return the matrix of structure constants
     * 
     *         private StructureConstantsMatrix getStructureConstantsMatrix() {
     * 
     *         return scm; }
     */

    /**
     * Return the Cayley table that indicates how to add roots in the root
     * system
     * 
     * @return the Cayley table for the roots in the root system
     * 
     *         public VectorCayleyTable getVectorCayleyTable() {
     * 
     *         return sums; }
     */

}